/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 * @Problem 136 - UglyNumber
 * @author Cesar Augusto Meneses Guzman
 * @version 1.0
 * @since 11 de Mayo de 2013
 */
public class UglyNumbers {
    public static void main( String args[] ) {
        final int n = 1499;
        int a[] = new int[ 1500 ];
        int p1, p2, p3, end;
        p1 = p2 = p3 = end = 0;
        a[ 0 ] = 1;
        while ( end < n ){
            while ( a[ p1 ] * 2 <= a[ end ] )
                ++p1;
            while ( a[ p2 ] * 3 <= a[ end ] )
                ++p2;
            while ( a[ p3 ] * 5 <= a[ end ] )
                ++p3;
            if ( a[ p1 ] * 2 < a[ p2 ] * 3 && a[ p1 ] * 2 < a[ p3 ] * 5 )
                a[ ++end ] = a[ p1++] * 2;
            else if ( a[ p2 ] * 3 < a[ p3 ] * 5)
                a[ ++end ] = a[ p2++ ] * 3;
            else
                a[ ++end ] = a[ p3++ ] * 5;
        }
        System.out.println("The 1500'th ugly number is " + a[ end ] + ".");
    }
}
